//
// Created by Administrator on 2021/5/6.
//


/*给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：
输入：s = "()"
输出：true

示例2：
输入：s = "()[]{}"
输出：true

示例3：
输入：s = "(]"
输出：false

示例4：
输入：s = "([)]"
输出：false

示例5：
输入：s = "{[]}"
输出：true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
#include <string>
#include <iostream>
#include <stack>
#include <unordered_map>

using namespace std;

class Solution {
public:
    bool isValid(string s) {
        stack<char> stack1;
        unordered_map<char, char> map1{{')', '('},
                                       {']', '['},
                                       {'}', '{'}};
        for (auto x:s) {
            if (x == '(' or x == '{' or x == '[') { // 左括号 直接入栈
                stack1.push(x);
            } else { // 右括号
                if (!stack1.empty() and stack1.top() == map1[x]) stack1.pop(); // 和栈顶做括号匹配 弹栈
                else return false; // 不匹配 返回错误
            }
        }
        return stack1.empty();
    }
};
class Solution2 { // 题解
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        unordered_map<char, char> pairs = {
                {')', '('},
                {']', '['},
                {'}', '{'}
        };
        stack<char> stk;
        for (char ch: s) {
            if (pairs.count(ch)) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            }
            else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};

int main() {
    Solution sol;
    cout << (sol.isValid("{}()") ? "true" : "false") << endl;
    cout << (sol.isValid("([)]") ? "true" : "false") << endl;
    cout << (sol.isValid("]") ? "true" : "false") << endl;
    return 0;
}